The H.264 video standard, also as known as MPEG-4 AVC, provides compression efficiency much higher than previous video coding standards, such as MPEG-2 and MPEG-4. In most video encoding algorithms, motion estimation (ME) is the most computationally expensive module. It is generally found that ME requires more than a half of the computational operations required for the whole encoding process. The H.264 video standard uses 7 types of motion search blocks (ranging from 4 by 4 to 16 by 16) and multiple reference pictures to achieve the higher compression efficiency. The MPEG-2 video standard uses only one type (16 by 16) of motion search block and a single reference picture. It is estimated that ME encoding module of the H.264 video standard requires much more computation than previous standards. Accordingly, some technique that will reduce the computation required for ME is needed.
In the H.264 video standard as well as many other video standards, each picture is divided into 16 by 16 pixels square partitions, called macroblocks. If inter-block prediction is allowed in the current picture, i.e. the current picture is P-picture or B-picture, each macroblock is further divided into motion search blocks whose size range from 16 by 16 pixels to 4 by 4 pixels. Each motion search block of the current picture can be predicted from the past or future reference pictures by estimating the motion between the current motion search block and the estimated block in the reference pictures. In order to choose the optimal motion vector, the cost value between the reference and the current motion search block is computed and compared. The cost value (COSTblock) is usually measured by the summation of the sum of absolute error (SAE) and the cost of motion vector (MVcos,) defined as follows:
                    COST        block            ⁡              (                  x          ,          y          ,          p          ,          N          ,          M          ,                      mv            x                    ,                      mv            y                          )              =                  SAE        ⁡                  (                      x            ,            y            ,            p            ,            N            ,            M            ,                          mv              x                        ,                          mv              y                                )                    +                        MV          cost                ⁡                  (                      p            ,                          mv              x                        ,                          mv              y                                )                                SAE      ⁡              (                  x          ,          y          ,          p          ,          N          ,          M          ,                      mv            x                    ,                      mv            y                          )              =                  ∑                  j          =          0                          N          -          1                    ⁢                        ∑                      i            =            0                                M            -            1                          ⁢                                                                      f                c                            ⁡                              (                                                      x                    +                    i                                    ,                                      y                    +                    j                                                  )                                      -                                          f                p                            ⁡                              (                                                      x                    +                                          mv                      x                                        +                                          mvp                      x                                        +                    i                                    ,                                      y                    +                                          mv                      y                                        +                                          mvp                      y                                        +                    j                                                  )                                                                  where: SAE( . . . ) is the sum of absolute error between the current motion search block whose top-left corner is (x,y) in the current picture and the predicted block whose top-left corner is (x+mvpx+mvx, y+mvpy+mvy) in the reference picture; fc(x,y) is the luminance samples (x,y) in the current picture; fp(x,y) is the luminance samples (x,y) in the reference picture; mvpx, mvpy are the horizontal and vertical motion vector predictors which can be computed from the motion vectors of neighboring motion search blocks; mvx, mvy are the horizontal and vertical motion vectors between the current and the predicted motion search block; N and M are the horizontal and vertical dimensions of the motion search block. The motion vector cost quantity MVcost(p,mvx,mvy) depends on the encoder implementation.
The SAE computation is performed in ME process within a macroblock with changing motion vectors, reference pictures, and motion search block size. After testing any combination of the motion search block size, the reference pictures and the motion vectors, the optimal combination is obtained by minimizing the cost value for the macroblock with the macroblock encoder quantity ME(COSTMB—ME). This can be computed by summing up the cost value for all the motion search block within the macroblock as in the following equation:COSTMB—ME(x,y)=ΣCOSTblock( . . . )
Meanwhile, the cost value of the macroblock with skip prediction mode (COST MB_SKIP) can be computed in a similar way as follows:
                    ⁢                            COST                      MB            ⁢                                                  ⁢            _            ⁢                                                  ⁢            SKIP                          ⁡                  (                      x            ,            y                    )                    =                        SAE          SKIP                ⁡                  (                      x            ,            y                    )                                        SAE        SKIP            ⁡              (                  x          ,          y                )              =                  ∑                  j          =          0                15            ⁢                        ∑                      i            =            0                    15                ⁢                                                                      f                c                            ⁡                              (                                                      x                    +                    i                                    ,                                      y                    +                    j                                                  )                                      -                                          f                                  skip                  ⁢                                                                          ⁢                  _                  ⁢                                                                          ⁢                  p                                            ⁡                              (                                                      x                    +                                          mvp                                              skip                        ⁢                                                                                                  ⁢                        _                        ⁢                                                                                                  ⁢                        x                                                              +                    i                                    ,                                      y                    +                                          mvp                                              skip                        ⁢                                                                                                  ⁢                        _                        ⁢                                                                                                  ⁢                        y                                                              +                    j                                                  )                                                                  where: SAEskip(x,y) is the sum of the absolute error between the current macroblock whose top-left corner is (x,y) in the current picture and the predicted macroblock whose top-left corner is labeled x+mvpskip—x, y+mvpskip—y in the reference picture; fskip—p(x,y) is the luminance samples (x,y) in the reference picture; mvpskip—x, and mvpskip—y are the horizontal and vertical motion vector predictors which can be computed from the motion vectors of temporally or spatially neighboring macroblocks depending on the coding environment.
FIG. 1 through FIG. 3 illustrate the typical flowchart of the optimal inter-block prediction mode (ordinary ME mode or skip prediction mode) selection of macroblock encoding in the H.264 video standard. FIG. 1 illustrates the prior art flowchart of the inter-block prediction process beginning at block 101. In block 102 the optimal ME cost value COSTMB—ME is computed from ME block size and motion vector selection. In block 103 the optimal SKIP cost value COSTMB—SKIP is computed for the skip prediction mode. The optimal inter-block prediction mode is selected by comparing in test block 104 the optimal cost value for macroblock encoding COSTMB—ME to that with skip prediction mode macroblock encoding COSTMB—SKIP. If COSTMB—ME is lower than COSTMB—SKIP then block 108 chooses the optimal set of ME block combination, reference pictures and motion vectors as the best prediction from the inter prediction of the macroblock. If COSTMB—ME is higher than COSTMB—SKIP, then test block 105 is selected to determine if there is a threshold of COSTMB—SKIP compared to cost T. If a threshold exists test block 106 compares COSTMB—SKIP to cost T. If COSTMB—SKIP is more than threshold cost T in test block 106, then the flow proceeds to block 108, which chooses the optimal set of ME block combination, reference pictures and motion vectors as the best prediction from the inter prediction of the macroblock. If COSTMB—SKIP is less than threshold cost T in test block 106, then block 107 chooses the skip prediction mode as the best prediction from the inter prediction of the macroblock. If no threshold T was found in test block 105, then test block 106 is bypassed to block 107. Block 107 selects the skip prediction mode as the best prediction from inter-prediction of the macroblock. The end block 109 completes the inter prediction mode selection for the macroblock.
FIG. 2 illustrates a flowchart of the method to obtain the COSTMB—ME from the ME block size and motion vector selection process. FIG. 2 begins at block 200. FIG. 2 illustrates the process to compute the COSTMB—ME with the changing combinations of ME block size within a macroblock, reference pictures, and motion vectors. This process requires a large amount of computation and returns the optimal COSTMB—ME along with the optimal combination of ME block size, reference pictures, and motion vectors. In FIG. 2, the four processes are initiated, each of which involve potential multiple iterations as evidenced by re-circulate paths 216 through 219. The initial four processes are:
(A) select a combination of ME block size in block 201;
(B) select one of the divided ME blocks in block 202;
(C) select a reference picture for the block Ref(Pic) and compute the motion vector predictor in block 203; and
(D) select a motion vector MV in block 204.
From the four selections in blocks 201 to 204, the data is available for step 205 to compute the cost value of COSTblock.
Test block 206 determines whether COSTblock is smaller than the candidate cost. If the result is Yes, then MV, Ref(Pic) and COSTblock are saved as the new candidate cost in block 207. If the result is NO, then MV, Ref(Pic) are tested further according to the prescriptions illustrated in test blocks 208, 209, and 210. A No result in any test block 208, 209, or 210 results in re-circulate via respective paths 216, 217, and 218 respectively. YES results in all test blocks 208, 209, and 210 allow the process to proceed without re-circulation to block 211. Block 211 computes the MB cost value COSTMB—ME. If COSTMB—ME it is smaller than the currently optional one, then block 211 qualifies it as the currently optimal MB cost value. Finally test block 212 determines if all combinations of ME block size are tested. A YES result in test block 212, ends the algorithm steps with the completion of ME block size and motion vector selection in end block 213. A NO result in test block 212, initiates a major re-circulation via path 219. From FIG. 2, it can be seen that the conventional process flow for ME block size and motion vector selection is a most complex algorithm.
In contrast to the process of FIG. 2, COSTMB—SKIP can be obtained from the skip prediction process described in FIG. 3. The skip prediction process initiates in block 300. The reference picture for the macroblock RefPicskip and MVPskip are computed in block 301. From the information computed in block 301, block 302 computes the MB cost value COSTMB—SKIP. The skip prediction computation concludes at end block 303.
In some implementations, the skip prediction mode will be selected (see 107 of FIG. 1) as the best inter-block prediction simply because the cost value with the skip prediction mode is the lowest. However, if the skip prediction mode is selected, it will skip coding not only the motion vector information but also the residual information. Accordingly, selecting skip prediction mode will reduce the output bit stream size, but will tend to deteriorate the image quality when compared to selecting other inter-block prediction modes if the cost values are equivalent. In order to minimize the image quality deterioration by selecting skip prediction mode, many implementations set the threshold value T to COSTMB—SKIP as described in test block 105 of FIG. 1. If T exists in the encoder and COSTMB—SKIP is larger than T, the optimal inter-block prediction with ME will be selected.
The fundamental concern here is that ME block size and motion vector selection, accomplished by the algorithm of FIG. 2, is a critical and time-consuming process. This makes it impractical to realize real-time encoding in most applications. Therefore, the computational reduction of ME block size and motion vector selection methodology providing high image quality and coding efficiency is desired.